GATE CSE 2012
Q2.
The worst case running time to search for an element in a balanced binary search tree with n2^{n} elements isQ3.
Let W(n) and A(n) denote respectively, the worst case and average case running time of an algorithm executed on an input of size n. Which of the following is ALWAYS TRUE?Q4.
A computer has a 256 KByte, 4-way set associative, write back data cache with block size of 32 Bytes. The processor sends 32 bit addresses to the cache controller. Each cache tag directory entry contains, in addition to address tag, 2 valid bits, 1 modified bit and 1 replacement bit. The size of the cache tag directory isQ5.
A computer has a 256 KByte, 4-way set associative, write back data cache with block size of 32 Bytes. The processor sends 32 bit addresses to the cache controller. Each cache tag directory entry contains, in addition to address tag, 2 valid bits, 1 modified bit and 1 replacement bit. The number of bits in the tag field of an address isQ6.
Consider the function f(x)=sin(x) in the interval x \in [\pi/4, 7\pi/4]. The number and location(s) of the local minima of this function areQ7.
The height of a tree is defined as the number of edges on the longest path in the tree. The function shown in the pseudocode below is invoked as height(root) to compute the height of a binary tree rooted at the tree pointer root. int height (treeptr n) { if (n == NULL) return -1; if (n \rightarrow left == NULL) if (n \rightarrow right == NULL) return 0; else return B1; else { h1 = height (n \rightarrow left); if (n \rightarrow right == NULL) return (1+h1); else { h2 = height (n \rightarrow right); return B2; } } } The appropriate expressions for the two boxes B1 and B2 areQ8.
Consider the 3 processes, P1, P2 and P3 shown in the table. The completion order of the 3 processes under the policies FCFS and RR2 (round robin scheduling with CPU quantum of 2 time units) areQ9.
What will be the output of the following C program segment? char inChar = 'A' ; switch ( inChar ) { case 'A' : printf ("Choice A\ n") ; case 'B' : case 'C' : printf ("Choice B") ; case 'D' : case 'E' : default : printf ( " No Choice" ) ; }